package com.mjlf.algorithms.sort;

import org.junit.Test;

/**
 * @auther a123
 * @create 2018-09-10 18:46
 * @desc 堆排序
 * 堆排序使用满二叉树中的最大堆或最小堆实现，其中最大堆满足父节点总是大于子节点，
 * 最小堆总是满足父节点小于子节点
 *
 * 完全二叉树使用数组存储数据，则有父节点下标 i , 左右子节点下标分别为 (2 * i + 1); (2 * i + 2)
 *
 * 使用堆排序原理其实有点像插入排序， 每次生成一个最大/最小堆， 然后将根节点与最后一个叶子节点进行更换位置
 * 如此往复，最终就拍好序了
 *
 * 需要注意的是， 其实在每次做最大最小堆的时候， 并没有形成完整的最大最小堆
 */
public class HeapSort {

    public static void sortByUp(Comparable[] elements){
        //这里需要注意的是最后元素的下标， 并非数组长度
        int lastIndex = elements.length - 1;
        int lastRootIndex = (lastIndex - 1) >> 1;
        for(int i = lastRootIndex; i >= 0; i --){
            makeMaxHeap(elements, i, lastIndex);
        }

        //依次从后往前更换每个最小最大堆的第一个元素， 是数组最后的元素有序
        for(int i = lastIndex; i > 0; i --){
            SortUtil.exch(elements, 0, i);
            makeMaxHeap(elements, 0, i - 1);
        }
    }


    /**
     * 堆排序
     *
     * @param elements
     */
    public static void sortByDown(Comparable[] elements) {
        int lastIndex = elements.length - 1;
        int lastRootIndex = (lastIndex - 1) >> 1;
        for(int i = lastRootIndex; i >= 0; i--){
            makeMinHeap(elements, i, lastIndex);
        }

        for(int i = lastIndex; i > 0; i --){
            SortUtil.exch(elements, 0, i);
            makeMinHeap(elements, 0, i - 1);
        }

        SortUtil.show(elements);
    }

    /**
     * 将指定子树最为最小堆
     *
     * @param elements
     * @param i         子树根节点下标
     * @param lastIndex 堆最后一个节点下标
     */
    public static void makeMinHeap(Comparable[] elements, int i, int lastIndex) {
        int left = i * 2 + 1;
        int right = left + 1;
        int minIndex = left;
        if(left > lastIndex){
            return;
        }
        if(right <= lastIndex && SortUtil.less(elements[right], elements[left])){
            minIndex = right;
        }
        if(SortUtil.less(elements[minIndex], elements[i])){
            SortUtil.exch(elements, minIndex, i);
            makeMinHeap(elements, minIndex, lastIndex);
        }
    }

    /**
     * 计算最大堆
     * @param elements
     * @param i
     * @param lastIndex
     */
    public static void makeMaxHeap(Comparable[] elements, int i, int lastIndex){
        int left = i * 2 + 1;
        int right = left + 1;
        int maxIndex = left;
        if(left > lastIndex){
            return;
        }
        if(right <= lastIndex && SortUtil.less(elements[left], elements[right])){
            maxIndex = right;
        }
        if(SortUtil.less(elements[i], elements[maxIndex])){
            SortUtil.exch(elements, i, maxIndex);
            makeMaxHeap(elements, maxIndex, lastIndex);
        }
    }

    @Test
    public void test(){
        Comparable[] elements = new Comparable[]{5,2,3,5,2,5,2,6,3,6};
        sortByUp(elements);
        SortUtil.show(elements);
    }
}
